﻿class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        if(nums.length<3||nums==null){
            return list;
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;//去除和上个数字相同
            }
            int l=i+1;
            int r=nums.length-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==0){
                    list.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //接下来还是进行去重
while(l<r&&nums[l]==nums[l+1]){
    l++;
}
while(l<r&&nums[r]==nums[r-1]){
    r--;
}
l++;
r--;
                }else if(sum>0){//sum>0,r应该左移
                 r--;
                }else{
                    l++;
                }
            }
        }
        return list;
    }
}